package org.usmile.algorithms.learn.单调栈;

import java.util.ArrayDeque;

/**
 * 找出数组中右边第一个比我大的元素
 */
public class RightFirstBigger {
    public int[] find(int[] nums) {
        int[] result = new int[nums.length];
        // 单调递减栈
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                result[stack.pop()] = i;
            }

            stack.push(i);
        }
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }

        return result;
    }
}
